#!/usr/bin/env python

# based on http://www.unixuser.org/~euske/doc/cdbinternals/pycdb.py.html
# pyoffwiki - offline wikipedia browser for the Irex Iliad
# Python implementation of cdb with sync points
# written by Amir Shimoni
# put into the public domain for any use
#   but please give credits to those who deserve them...
# files should be used compressed... otherwise extra sync data wastes ALOT of space
# sync points, random, binary search 


# calc hash value with a given key
def calc_hash(s):
  return reduce(lambda h,c: (((h << 5) + h) ^ ord(c)) & 0xffffffffL, s, 5381)

# cdbget(fp, basepos, key)
def cdbget(fp, pos_header, k):
  from struct import unpack

  r = []
  h = calc_hash(k)
  
  fp.seek(pos_header + (h % 256)*(4+4))
  (pos_bucket, ncells) = unpack('<LL', fp.read(4+4))
  if ncells == 0: raise KeyError

  start = (h >> 8) % ncells
  for i in range(ncells):
    fp.seek(pos_bucket + ((start+i) % ncells)*(4+4))
    (h1, p1) = unpack('<LL', fp.read(4+4))
    if p1 == 0: raise KeyError
    if h1 == h:
      fp.seek(p1+8)
      (klen, vlen) = unpack('<LL', fp.read(4+4))
      k1 = fp.read(klen)
      v1 = fp.read(vlen)
      if k1 == k:
        r.append(v1)
        break
  else:
    raise KeyError
      
  return r

# get random key... 
def cdbrandom(fp):
  from struct import unpack
  import random
  random.seed()
  h = random.randint(0, 255)
  for aa in range(256):
    fp.seek(((h+aa) % 256)*(4+4))
    (pos_bucket, ncells) = unpack('<LL', fp.read(4+4))
    if ncells == 0: continue

    start = random.randint(0, ncells-1)
    for i in range(ncells):
      fp.seek(pos_bucket + ((start+i) % ncells)*(4+4))
      (h1, p1) = unpack('<LL', fp.read(4+4))
      if p1 == 0: continue
      else:
        fp.seek(p1+8)
        (klen, vlen) = unpack('<LL', fp.read(4+4))
        k1 = fp.read(klen)
        v1 = fp.read(vlen)
        return k1
      
  return None

def cdbGetDataEnd(fp):
  from struct import unpack
  import sys
  endspot = sys.maxint
  fp.seek(0)
  for aa in range(256):
    (pos_bucket, ncells) = unpack('<LL', fp.read(4+4))
    if ncells == 0: continue
    if pos_bucket < endspot: endspot = pos_bucket
  return endspot

def cdbprintkeys(fp):
  from struct import unpack
  endspot = cdbGetDataEnd(fp)
  #print endspot
  pos_bucket = 256*8
  fp.seek(pos_bucket)
  while pos_bucket < endspot:
    fp.read(8) # should be all 0xff
    (klen, vlen) = unpack('<LL', fp.read(4+4))
    k1 = fp.read(klen)
    v1 = fp.read(vlen)
    pos_bucket += klen+vlen+8+8
    print repr(k1)

def cdbSearchGetData(fp, pos):
  from struct import unpack
  fp.seek(pos)
  fp.read(8) # should be all 0xff
  (klen, vlen) = unpack('<LL', fp.read(4+4))
  k1 = fp.read(klen)
  v1 = fp.read(vlen)
  recordlen = 8+8+klen+vlen
  return (k1,v1, recordlen)


def cdbSearchRecur(fp, key, minpos, maxpos):
  if minpos == maxpos: return minpos
  mid = (minpos+maxpos)/2
  fp.seek(mid)
  ffcount = 0;
  while True:
    tc = fp.read(1)
    mid = mid + 1
    #print repr(tc)
    if tc == '\xff': ffcount = ffcount + 1
    else: ffcount = 0
    if ffcount == 8:
      newmid = mid - 8
      break
    if mid >= maxpos:
      # we've reached the end of the block...
      # should almost never happen, so we search the first element...
      newmid = minpos
      ffcount = 8
      break
      
  a,b,c  = cdbSearchGetData(fp, newmid)
  #print a
  if a == key: return newmid
  elif key > a: return cdbSearchRecur(fp, key, newmid+c, maxpos)
  else: return cdbSearchRecur(fp, key, minpos, newmid)

def cdbSearch(fp, key):
  endspot = cdbGetDataEnd(fp)
  return cdbSearchRecur(fp, key, 256*8, endspot)

def cdbGetKeyList(fp, startpos, size):
  maxpos = cdbGetDataEnd(fp)
  minpos = 256*8
  if startpos < minpos: startpos = minpos
  if startpos > maxpos: startpos = minpos
  fp.seek(startpos)
  ffcount = 0;
  while True:
    tc = fp.read(1)
    startpos += 1
    #print repr(tc)
    if tc == '\xff': ffcount = ffcount + 1
    else: ffcount = 0
    if ffcount == 8:
      startpos  -= 8
      break
    if startpos >= maxpos:
      # nothing...
      return None
  
  result = []
  for aa in range(size):
    a,b,c  = cdbSearchGetData(fp, startpos)
    result.append(a)
    startpos += c
    if startpos >= maxpos: break;

  return [result, startpos]
